How to Better Use Expert Advice

This work is concerned with online learning from expert advice. Extensive work on this problem generated numerous expert advice algorithms whose total loss is provably bounded above in terms of the loss incurred by the best expert in hindsight. Such algorithms were devised for various problem variants corresponding to various loss functions. For some loss functions, such as the square, Hellinger and entropy losses, optimal algorithms are known. However, for two of the most widely used loss functions, namely the 0/1 and absolute loss, there are still gaps between the known lower and upper bounds.In this paper we present two new expert advice algorithms and prove for them the best known 0/1 and absolute loss bounds. Given an expert advice algorithm ALG, the goal is to form an upper bound on the regret L _ALG – L* of ALG, where L _ALG is the loss of ALG and L* is the loss of the best expert in hindsight. Typically, regret bounds of a canonical form C · are sought where N is the number of experts and C is a constant. So far, the best known constant for the absolute loss function is C = 2.83, which is achieved by the recent IAWM algorithm of Auer et al. (2002). For the 0/1 loss function no bounds of this canonical form are known and the best known regret bound is , where C ₁ = e – 2 and C ₂ = 2 . This bound is achieved by a P-norm algorithm of Gentile and Littlestone (1999). Our first algorithm is a randomized extension of the guess and double algorithm of Cesa-Bianchi et al. (1997). While the guess and double algorithm achieves a canonical regret bound with C = 3.32, the expected regret of our randomized algorithm is canonically bounded with C = 2.49 for the absolute loss function. The algorithm utilizes one random choice at the start of the game. Like the deterministic guess and double algorithm, a deficiency of our algorithm is that it occasionally restarts itself and therefore forgets what it learned. Our second algorithm does not forget and enjoys the best known asymptotic performance guarantees for both the absolute and 0/1 loss functions. Specifically, in the case of the absolute loss, our algorithm is canonically bounded with C approaching and in the case of the 0/1 loss, with C approaching 3/ . In the 0/1 loss case the algorithm is randomized and the bound is on the expected regret.     

Verifying functions in online stock trading systems

Temporal colored Petri nets, an extension of temporal Petri nets, are introduced in this paper. It can distinguish the personality of individuals (tokens), describe clearly the causal and temporal relationships betwee nevents in concurrent systems, and represent elegantly certain fundamental properties of concurrent systems, such as eventuality and fairness. The use of this method is illustrated with an example of modeling and formal verification of an online stock trading system. The functional correctness of the modeled system is formally verified based on the temporal colored Petri net model and temporal assertions. Also, some main properties of the system are analyzed. It has been demonstrated sufficiently that temporal colored Petri nets can verify efficiently some time-related properties of concurrent systems, and provide both the power of dynamic representation graphically and the function of logical inference formally. Finally. future work is described.     

基于半信任模型的无收据的电子投票

利用同态EIGamal加密、门限EIGamal加密和同指数知识证明等技术,给出了一种无收据的电子投票方案．该方案同时保证了选票的秘密性、广义可验证性和公平性．与以前协议不同的是,所提的方案基于半信任模型,即投票者不必无条件地信任所谓的“可信赖第三方”．文中首先给出了“半信任”的定义,然后证明了所提方案在半信任模型下该方案仍然满足无收据性,从而防止了选举中的“选票买卖”、“强迫选举”等犯罪行为．     

利用SST89C58的IAP／ISP实现的在线仿真技术

“在线仿真”技术提出了一种代替仿真器的方法,其关键部分是监控程序、仿真程序和PC机与单片机的通信,在两部分程序相配合的情况下,利用IAP／ISP技术即可对系统进行实时调试。用户可不必购买仿真器,从而节省费用,对学校的单片机教学提供了一条新的途径。     

A chaos-based image encryption algorithm using alternate structure

Combined with two chaotic maps, a novel alternate structure is applied to image cryptosystem. In proposed algorithm, a general cat-map is used for permutation and diffusion, as well as the OCML (one-way coupled map lattice), which is applied for substitution. These two methods are operated alternately in every round of encryption process, where two subkeys employed in different chaotic maps are generated through the masterkey spreading. Decryption has the same structure with the encryption algorithm, but the masterkey in each round should be reversely ordered in decryption. The cryptanalysis shows that the proposed algorithm bears good immunities to many forms of attacks. Moreover, the algorithm features high execution speed and compact program, which is suitable for various software and hardware applications.     

基于C/S结构的公安综合移动警务系统的混合加密方案

为了实现基于C/S结构的公安综合移动警务系统信息的加密传输,设计并实现了一种基于AES算法和Morii-Kasahara算法的混合加密方案;该方案消除了对称加密算法密钥管理复杂;非对称加密算法加解密速度慢,占用内存大的缺点;并且采用查表和并行处理技术可以提高Morii-Kasahara算法的加密速度,通过改变Morii-Kasahara算法求取模数的方法可以提高算法安全性;实践证明,该方案具有算法安全性高、运算速度快、带宽需求低、密钥管理方便、需求存储空间小等优点,适合公安综合移动警务系统信息的加密传输.     

对一种基于混沌映射的对称图像加密算法的改进

文[1]提出了一种基于3D Cat映射的对称图像加密算法，文[2]对其安全性进行了分析，指出该算法在抗选择明文攻击能力方面性能比较差。本文在文[1]的基础上，提出了一种改进的对称图像加密算法。在本算法中，通过复合离散混沌系统隐藏混沌序列产生时所经历的迭代次数，来避免文[2]的基于符号动力学的密码分析。理论分析和仿真实验表明，本文提出的改进算法在保持了原来算法的各种抗攻击能力性能的同时，进一步提高了原算法的抗选择明文攻击能力。     

Improving the Performance of Online Auctions Through Server-side Activity-based Caching

Online auction sites have very specific workloads and user behavior characteristics. Previous studies on workload characterization conducted by the authors showed that (1) bidding activity on auctions increases considerably after 90% of an auction’s life time has elapsed, (2) a very large percentage of auctions have a relatively low number of bids and bidders and a very small percentage of auctions have a high number of bids and bidders, (3) prices rise very fast after an auction has lasted more than 90% of its life time. Thus, if bidders are not able to successfully bid at the very last moments of an auction because of site overload, the final price may not be as high as it could be and sellers, and consequently the auction site, may lose revenue. In this paper, we propose server-side caching strategies in which cache placement and replacement policies are based on auction-related parameters such as number of bids placed or percent remaining time till closing time. A main-memory auction cache at the application server can be used to reduce accesses to the back-end database server. Trace-based simulations were used to evaluate these caching strategies in terms of cache hit ratio and cache efficiency. The performance characteristics of the best policies were then evaluated through experiments conducted on a benchmark online auction system.     

大规模蠕虫在线追踪培养皿

提出了一个用于反向追踪大规模网络蠕虫传播的虚拟实验环境，能够用于网络蠕虫检测和防御实验。实验环境使用虚拟机技术，虚拟大量主机和网络设备参加，尽量符合网络实际。在可控的范围内，使用真实的感染代码引发大规模蠕虫的爆发，观测蠕虫的传播过程。实验环境中可以发现蠕虫的传播特性，实时收集网络蠕虫的流量数据和感染过程。